Skip to main content

Microsoft Research Video

More than 1,100 brilliant scientists and engineers push the boundaries of computing in multiple research areas and include contributions to Kinect for Xbox 360, work to develop an HIV vaccine, and advancing education techniques in rural communities.

PART OF
Computers & Technology
More right-solid
More right-solid
SHOW DETAILS
up-solid down-solid
eye
Title
Date Archived
Creator
Microsoft Research Video
by Microsoft Research
movies
eye 140
favorite 0
comment 0
"Kristin Lauter chairs this session at Faculty Summit 2011, which includes the following presentations. Cryptographic Cloud Storage and Services—Kristin Lauter, Microsoft Research Encryption as Access Control for Cloud Security—Carl Gunter, University of Illinois The Economics of Cloud Computing: Why a Brooklyn Latte Buys a Million Unforgettable Signatures—Radu Sion, Stony Brook University *
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Kristin Lauter, Carl Gunter,...
Predicate EncryptionEmily Shen, MITPredicate encryption is a new encryption paradigm which gives a master secret key owner fine-grained control over access to encrypted data. The master secret key owner can generate secret key tokens corresponding to predicates. An encryption of data x can be evaluated using a secret token corresponding to a predicate f; the user learns whether the data satisfies the predicate, i.e., whether f(x) = 1. This talk will survey recent results in this area, and...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Emily Shen, Seny Kamara, and...
Microsoft Research Video
movies
eye 74
favorite 0
comment 0
Joint work with Tamara Rezk and Gurvan le Guernic (MSR-INRIA Joint Centre http://msr-inria.inria.fr/projects/sec) We relate two notions of security: one simple and abstract, based on information flows in programs, the other more concrete, based on cryptography. In language-based security, confidentiality and integrity policies specify the permitted flows of information between parts of a system with different levels of trust. These policies enable a simple treatment of security, but their...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Cedric Fournet
AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2 128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2 176 and 2 100 time, respectively. While these complexities are...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Orr Dunkelman
Microsoft Research Video
movies
eye 64
favorite 0
comment 0
Much of the research in number theory, like mathematics as a whole, has been inspired by hard problems which are easy to state. A famous example is "Fermat's Last Theorem". Starting in the 1970's number theoretic problems have been suggested as the basis for cryptosystems, such as RSA and Diffie-Hellman. In 1985 Koblitz and Miller independently suggested that the discrete logarithm problem on elliptic curves might be more secure than the "conventional" discrete logarithm on...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Victor Miller
Microsoft Research Video
by Microsoft Research
movies
eye 61
favorite 0
comment 0
Most modern cryptography, and 'public-key' crypto in particular, is based on mathematical problems that are conjectured to be infeasible (e.g., factoring large integers). Unfortunately, standard public-key techniques are often too inefficient to be employed in many environments; moreover, all commonly used schemes can in principle be broken by quantum computers. This talk will review my recent work on developing new mathematical foundations for cryptography, using geometric objects called...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Chris Peikert
Pairing based cryptography has resulted in a number of breakthrough results, including some major developments in the area of zero knowledge proof systems. A zero knowledge proof system allows a party to prove that a statement is true without revealing any other information. Zero knowledge proofs are used in everything from identification protocols (allowing a party to prove that he is who he claims to be) and encryption schemes with stronger security properties, to securing protocols against...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Melissa Chase
Classical newforms are cusp forms on congruence subgroups of SL(2,Z) that are eigenvectors for the Hecke operators. These modular forms give rise to two-dimensional representations of the absolute Galois group of the rational field. Conversely, if one starts with a semisimple two-dimensional representation of this Galois group over a finite field, the representation should arise from a newform if a mild necessary condition (involving complexconjugation) is satisfied. When the representation is...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Kenneth A. Ribet
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Rene Schoof
Microsoft Research Video
movies
eye 57
favorite 0
comment 0
I will present a retrospective of aspects of my thesis, in light of applications in the last 14 years since its birth. In particular, I will focus on explicit isogenies, moduli of elliptic curves and CM structure, the "local" Galois module structures of l-torsion and l-isogeny graphs, and "global" structure of action visa class groups and isogenies. The focus will be directed principally towards ordinary elliptic curves over finite fields, but I will discuss briefly the...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, David Kohel
Fully Homomorphic Encryption over the IntegersVinod Vaikuntanathan, Microsoft ResearchWe construct a simple fully homomorphic encryption scheme, using only elementary modular arithmetic. The security of our scheme relies on the hardness of the approximate integer greatest common divisors (gcd) problem – namely, given a list of integers that are "near-multiples" of a hidden integer, output that hidden integer.Joint work with Marten van Dijk, Craig Gentry, and Shai Halevi.Bi-Deniable...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Vinod Vaikuntanathan, Chris...
Microsoft Research Video
movies
eye 53
favorite 0
comment 0
The Advanced Encryption Standard (AES) is one of the most popular ciphers in the world and is widely used for both commercial andgovernment purposes. Since it became a standard in 2001, the progress in its cryptanalysis has been very slow. Even the best attacks, which exist only on reduced versions, were impractical.New attacks are based on ideas from the cryptanalysis of hash functions. We show how the principle of local collisions exhibits non-tivial properties of the full cipher, and how an...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Dmitry Khovratovich
Microsoft Research Video
movies
eye 49
favorite 0
comment 0
This is a report on joint work with Everett Howe and Kristin Lauter. I will discuss the genus 2 analogue of the problem of efficiently constructing an elliptic curve over a finite field with a prescribed number N of points. If N is provided with its prime factorization, the elliptic construction I gave with Broker is heuristically polynomial time outside a zero density subset of input values N. I will explain why the analogous construction to obtain abelian surfaces of given order N is...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Peter Stevenhagen
Microsoft Research Video
movies
eye 48
favorite 0
comment 0
The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks: Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v= m - 2*log(1/e), meaning that the entropy loss L = m-v= 2*log(1/e). Large Seed Length: the seed length n of universal hash function required by the LHL must be linear...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Yevgeniy Dodis
Microsoft Research Video
movies
eye 41
favorite 0
comment 0
6:30 – 6:50 PMScott Vanstone Award Lecture Session Chair: Neil Koblitz 6:50 – 9:00 PMRump Session Session Chair: Daniel J. Bernstein ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Scott Vanstone, Daniel J....
In 2000, Galbraith and McKee conjectured a formula estimating the probability of primality of the number of rational points on an elliptic curve over a finite field. Their heuristic derivation was based on an analytic class number formula counting bivariate quadratic forms up to equivalence. We will give alternative heuristics in favor of the conjecture, based on a random matrix model. This approach seems better-suited for generalizing the conjecture to curves of higher genus. We will then...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Wouter Castryck
Microsoft Research Video
movies
eye 38
favorite 0
comment 0
This is a report on joint work with Kristin Lauter and Peter Stevenhagen. Broker and Stevenhagen have shown that in practice it is not hard to produce an elliptic curve (over some finite field) with a given number N of points, provided that the factorization of N is known. In his talk this week, Stevenhagen will show that the natural generalization of this method to produce genus-2 curves with a given number of points on their Jacobian is an exponential algorithm. I will consider the related...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Everett Howe
Recently, Gaudry and Diem have proposed an index calculus method for the resolution of the DLP on elliptic curves defined over extension fields. In this talk, I will first present a variant of this method that enables to decrease the asymptotic complexity of the DLP on E(Fqn) for a large range of q and n, then introduce a second improvement provided by the use of F4 traces for polynomial system solving. Finally, I will give a practical example of our index calculus variant to the...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Vanessa Vitse
Microsoft Research Video
movies
eye 38
favorite 0
comment 0
Sage is a large mathematical software project based at the University of Washington that is funded by Microsoft, the National Science Foundation, and other organizations. The longterm goal of Sage is provide a viable free alternative to Matlab, Maple, Mathematica, and Magma. In this talk I will answer the question 'what does Sage do right now?' If you're a Matlab, Maple, Mathematica, or Magma user, you won't want to miss this talk. http://sagemath.org ©2009 Microsoft Corporation. All rights...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, William Stein
The conventional wisdom in cryptography is that for greatest security one should choose parameters as randomly as possible. In particular, in elliptic and hyperelliptic curve cryptography this means making random choices of the coefficients of the defining equation. One can often achieve greater efficiency by working with special curves, but that should be done only if one is willing to risk a possible lowering of security. Namely, the extra structure that allows for greater efficiency could...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Neal Koblitz
Microsoft Research Video
movies
eye 37
favorite 0
comment 0
A classical approach of constructing elliptic curves that can be used for cryptographic purposes relies on the theory of complex multiplication. A key ingredient in the algorithm is to compute the Hilbert class polynomial P D for a suitable discriminant D. The polynomial P D has integer coefficients, and is the minimal polynomial of the modular j-value j(O D ) for the imaginary quadratic order O D of discriminant D. The polynomial P D can be computed using complex analytic techniques. In this...
Topics: Microsoft Research, Microsoft Research Video Archive, Jennifer Chayes/Kristin Lauter, Reinier Broker
Elliptic curves with complex multiplication: history and perspectivesThe theory of complex multiplication on curves is very old and rich, going back at least to Klein. Since then, many authors have been developing the theory, in parallel with quite a heavy load of computations and formulas (by hand!). Soon after Schoof's 1985 major article, reduction of curves with complex multiplication over finite fields were used to prove the primality of special or general numbers, and the corresponding...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Francois Morain
Microsoft Research Video
movies
eye 35
favorite 0
comment 0
Anonymous credential systems allow users to anonymously obtain credentials from organizations, and to anonymously and unlinkably prove possesion of valid credentials. Often in practice, however, a user authenticates using some credential chain: a root organization gives a credential to an intermediate party who can in turn use this to issue credentials to user.We address this problem by presenting the first efficient delegatable anonymous credential scheme. In such a scheme, a party can receive...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Melissa Chase
This talk is about efficient pairing computation on elliptic curves. I will discuss particularly implementation-friendly curves, the use of the polynomial parameter representation to compute pairings on BN curves, and reasons to use affine coordinates for pairings at high security levels. This contains joint work with P. Barreto, G. Pereira, M. Simplício Jr, P. Schwabe, R. Niederhagen, K. Lauter, and P. Montgomery. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Michael Naehrig
Microsoft Research Video
movies
eye 34
favorite 0
comment 0
You use cryptography every time you make a credit card-based Internet purchase or use an ATM machine. But what is it? How does it work and how do we know when it is secure? This talk is an introduction to the problems, issues, colorful personalities and advances in this area. We will explain how cryptography is a marriage of mathematics and computer science. We will explain what are proofs of security and their value and limitations in providing security assurance. We will see how gaps between...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Mihir Bellare
Let q=p r be a prime power and F q be the finite field with q elements. We study the multiplication of two polynomials in F q [X] , with degree ≤ n-1 , modulo an irreducible polynomial of degree n , namely the multiplication in the finite field F q n . We want to find a multiplication algorithm involving two variables in F q n minimizing the number of bilinear multiplications (i.e. involving two variables) in F q . We don't take in account multiplications of a variable in F q by a constant in...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Robert Rolland
Microsoft Research Video
by Microsoft Research
movies
eye 33
favorite 0
comment 0
Sage (http://sagemath.org) is the most feature rich general purpose free open source software for computing with elliptic curves. In this talk, I'll describe what Sage can compute about elliptic curves and how it does some of these computation, then discuss what Sage currently can't compute but should be able to (e.g., because Magma can). ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, William Stein
Microsoft Research Video
movies
eye 33
favorite 0
comment 0
The focus of the talk is deterministic public-key encryption schemes. Besides being interesting from theoretical and historical perspectives, the deterministic encryption primitive has applications to fast and secure search on remote data. We study several new notions of security for deterministic encryption and relations among them. We present several very efficient deterministic encryption schemes that provably satisfy the strongest-possible security definition (in the random oracle model)....
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Alexandra Boldyreva
Microsoft Research Video
movies
eye 33
favorite 0
comment 0
Cryptographic hash functions are a fundamental primitive, utilized in numerous security applications. With the recent attacks against many widely deployed hash functions (e.g., MD5, SHA-1), the search is on for new, secure hash functions to re-establish security of all the various protocols that rely on them. At the same time, hash functions like SHA-1 have seen expanded usage into applications that demand security properties not handled by traditional design approaches. In this talk, I'll...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter/Anton Mityagin, Tom Ristenpart
Microsoft Research Video
movies
eye 33
favorite 0
comment 0
Many trading strategies are based on perceived relationships between the prices of different assets. Some of these relationships are based on fundamental relationships e.g. when oil goes up oil companies do better but transportation companies like airlines do worse. Most of the strategies based on fundamental relationships have been exploited to the point where they are no longer profitable. Using methods developed by Robert Engle and Steve Grainger (for which they received the Nobel Memorial...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Niels Nygaard
Microsoft Research Video
by Microsoft Research
movies
eye 32
favorite 0
comment 0
The parametrization of ideal classes of quadratic rings by binary quadratic forms has been an important tool for computing class numbers of quadratic fields. We will discuss how in this classical theorem, the integers can be replaced by the projective line, quadratic rings are then replaced by hyperelliptic curves, and ideal classes are replaced by line bundles on those curves. This gives a very explicit parametrization of line bundles on hyperelliptic curves by certain forms that are...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Melanie Matchett Wood
Microsoft Research Video
movies
eye 31
favorite 0
comment 0
10:00 - 10:45 David Molnar, Microsoft Research Some vulnerabilities in current systems 10:45 - 11:15 Paul Miller, Washington State Voting Systems Manager Issues and research directions from the public sector ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Sanjit A. Seshia, David...
Microsoft Research Video
by Microsoft Research
movies
eye 30
favorite 0
comment 0
The values of the elliptic modular function j at imaginary quadratic numbers τ are called singular moduli. They are of fundamental importance in the study of elliptic curves and in algebraic number theory, including the study of elliptic curves over finite fields. The theorem of Gross and Zagier has provided striking congruences satisfied by these numbers. Various aspects of this theorem were generalized in recent years by Jan Bruinier and Tonghai Yang and by Kristin Lauter and the speaker....
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Eyal Goren
Microsoft Research Video
movies
eye 30
favorite 0
comment 0
Emerging trends in computation such as cloud computing, virtualization, and trusted computing require that computation be carried out in remote and hostile environments, where attackers have unprecedented access to the devices, the data and the programs. This poses new problems and challenges for cryptography. In this talk, I will present two such challenges, and my recent work towards solving them. Protecting against Side-channel Attacks: Computing devices leak information to the outside world...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Vinod Vaikuntanathan
Segment II 11:10 am – 12:30 pmWriting on Wind and Water: Enforcing File Robustness in the CloudAri Juels, RSA LaboratoriesThe Cloud abstracts away infrastructural complexity for the benefit of tenants. But to tenants' detriment, it can also abstract away vital security information. In this talk, I discuss several protocols for remote testing of cloud storage integrity and robustness. Executing these protocols without detailed infrastructural knowledge or trust in cloud providers, clients or...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Ari Juels and Charalampos...
Microsoft Research Video
movies
eye 28
favorite 0
comment 0
I'll begin by describing SANDstorm, the Sandia entry in the NIST Hash Function competition. Next, I borrow an idea of Peter Montgomery's to speed up elliptic curve calculations (Affine Strikes Back!). Finally, I'll offer a frisson of lighter math fare. ©2009 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Rich Schroeppel
Microsoft Research Video
movies
eye 26
favorite 0
comment 0
Over the past decade the cryptographic research community has made impressive progress in developing new cryptographic protocols. This work has advanced our understanding of basic technologies such as public key encryption, key agreement, and digital signatures. Moreover, it has given us entirely new paradigms for securing data, such as Attribute Based Encryption, anonymous credentials and techniques for computing on encrypted data. Despite these advances, only a trickle of new cryptographic...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Matthew Green
After describing some joint work with Menezes in which isogenies are used to show that conventional wisdom about parameter selection might sometimes be wrong, I'll shift gears and make some comments on how easy it is to get things badly wrong in cryptography. I'll illustrate by giving a brief survey of some of the many misjudgments I've made over the years. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Neal Koblitz
Virtual Machine Reset Vulnerabilities and Hedged Cryptography Tom Ristenpart, UC San Diego Virtual machines are widely used to, for example, support cloud computing services and improve home desktop security. In this talk I'll present recent work on showing a new class of vulnerabilities, termed VM reset vulnerabilities, that arise due to reuse of VM snapshots. A snapshot is the saved state of a VM, which can include caches, memory, persistent storage, etc. A reset vulnerability occurs when...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Tom Ristenpart, Krzysztof...
Microsoft Research Video
movies
eye 25
favorite 0
comment 0
I will present an algorithm which computes Hilbert modular forms on real quadratic fields. The computations exploit the Jacquet-Langlands correspondence to switch to definite quaternions algebras and are intimately related to the computations of the class numbers of the latter. We will illustrate our discussion with several examples. ©2006 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Lassina Dembele
Microsoft Research Video
by Microsoft Research
movies
eye 24
favorite 0
comment 0
ECC2K-130 is the smallest unsolved Certicom discrete-logarithm challenge. Certicom originally stated that breaking ECC2K-130 was "infeasible" and would require 2700000000 machine days. This talk reports on an ongoing joint project by researchers from 12 different universities to break ECC2K-130. The project has increased our knowledge of the mathematical speedups for attacking elliptic-curve cryptosystems, has led to a new representation for finite fields in 'optimal polynomial...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Tanja Lange
Microsoft Research Video
by Microsoft Research
movies
eye 23
favorite 0
comment 0
This talk will consist of a series of light mini-talks inspired by Atkin's papers on recognizing primes (1982, "On a primality test of Solovay and Strassen"; 1995, "Intelligent primality test offer"), proving primes to be prime (1993, "Elliptic curves and primality proving"), factoring integers into primes (1993, "Finding suitable curves for the elliptic curve method of factorization"), and enumerating primes (2004, "Prime sieves using binary...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Daniel J. Bernstein
'Secure Computation' has been a classic and central question in modern cryptography with a large set of potential applications.Mining large genomic databases, private scientific computation, and studying properties of shared networks are just a few examples.Unfortunately, the majority of the constructions in this area have not made their way into practice, primarily due to their inefficiency. In this talk, I first outline three different approaches toward designing more practical protocols, and...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Payman Mohassel
Microsoft Research Video
movies
eye 22
favorite 0
comment 0
1:00 - 1:30 Ron Rivest, MITScantegrity: overview and open problems ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Ron Rivest
This presentation has two parts. The first half discusses the major factorization algorithms when ECM was discovered in 1985, stressing the similarities between ECM and P +- 1. The second half describes the recent discoveries of six large Mersenne factors using ECM on a network of PlayStations. This is joint work with Joppe W. Bos, Thorsten Kleinjung, and Arjen K. Lenstra from EPFL. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Winnie Li
Microsoft Research Video
movies
eye 22
favorite 0
comment 0
An elliptic divisibility sequence is an integer recurrence sequence related to the multiples of a rational point on an elliptic curve. We generalise this definition to higher dimensions: an elliptic net is a map from Z n to Z encoding information about the Mordell-Weil group. This gives new methods of computation on elliptic curves, including a new algorithm to compute the Tate pairing for pairing-based cryptography. ©2007 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter/Jennifer Chayes, Katherine...
Microsoft Research Video
movies
eye 21
favorite 0
comment 0
Motivated by her joint work with H. Cohn on genus two curve crypotosystem, Lauter gave a very inspiring conjecture on the CM value of Igusa invariants. They need to compute these values to construct `good' genus two curves. This conjecture led to study of arithmetic intersection on an arithmetic 3-fold (Hilbert modular surface). Recently, I proved an arithmetic intersection formula, which leads to proof of Lauter's conjecture. The formula also leads to the first non-abelian generalization of...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Tonghai Yang
Microsoft Research Video
movies
eye 21
favorite 0
comment 0
Elliptic curves E can be given by plane projective cubic curves and so seem to be very simple objects. A first hint for more structure is that there is an algebraic addition law for the rational points. In fact, there is a natural isomorphism of E with its Jacobian variety, and so E is at the same time a curve of low degree and an abelian variety of smallest possible dimension. This is the reason for a very rich and deep theory behind making elliptic curves to ideal objects for both theoretical...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Gerhard Frey
Cloudy, Without a Chance of Data Loss - ImplementationKevin Bowers, RSA LaboratoriesCloud storage promises to provide consumers with cheap storage that can be accessed at any time, from anywhere. The appeal of such a system is easy to understand, as too is the fear people have of outsourcing the storage of valuable data. Recent failures and loss of data by cloud storage providers has done little to ease these fears.Fear is often a product of the unknown. In this talk we present several newly...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Kevin Bowers and Tom Roeder
Microsoft Research Video
by Microsoft Research
movies
eye 21
favorite 0
comment 0
As a tribute to Oliver Atkin, I will be surveying his work; I will also be including some biographical details. As that would be far too much to talk about, I will be forced to be selective, and will mainly concentrate on work he did in his earlier years, including a bit about what may have influenced him to do that work, and what his work led to. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Bryan Birch
Microsoft Research Video
by Microsoft Research
movies
eye 21
favorite 0
comment 0
This presentation has two parts. The first half discusses the major factorization algorithms when ECM was discovered in 1985, stressing the similarities between ECM and P +- 1. The second half describes the recent discoveries of six large Mersenne factors using ECM on a network of PlayStations. This is joint work with Joppe W. Bos, Thorsten Kleinjung, and Arjen K. Lenstra from EPFL. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Peter Montgomery
Microsoft Research Video
movies
eye 20
favorite 0
comment 0
The DLP with auxiliary inputs is to find α when g α i (i=0,1,2,…,d) as well as g, g α are given. Recently, numerous cryptosystems are designed on a weaker variant of this problem. One example is the strong Diffie-Hellman problem. It has been shown that the complexity of this problem is lower than the original DLP by upto √ d group operations when p-1 or p+1 has an appropriate divisor. In this talk, we present a generalization of this algorithm, which can be applied even when p-1 and p+1$...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Jung Hee Cheon
Microsoft Research Video
movies
eye 19
favorite 0
comment 0
We present HIBE and ABE schemes which are “unbounded" in the sense that the public parameters do not impose additional limitations on the functionality of the systems. In all previous constructions of HIBE in the standard model, a maximum hierarchy depth had to be fixed at setup. In all previous constructions of ABE in the standard model, either a small universe size or a bound on the size of attribute sets had to be fixed at setup. Our constructions avoid these limitations. We use a...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Brent Waters
Microsoft Research Video
movies
eye 19
favorite 0
comment 0
We give a survey on old and new results on relations between geometric invariants of principally polarized supersingular abelian varieties and arithmetic invariants of quaternion hermitian forms (such as the numbers of polarizations and irreducible components of the supersingular locus, the field of definition, existence of curves with many rational points, class numbers, type numbers, and Hecke operators). Conjecturally quaternion hermitian forms are related with Siegel modular forms by...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Tomoyoshi Ibukiyama
Computing genus 2 curves from invariants on the Hilbert moduli spaceJoint work with Tonghai Yang (University of Wisconsin USA); he was originally scheduled to present this work.We give a new method for generating genus 2 curves over a finite field with a given number of points on the Jacobian of the curve. We define two new invariants for genus 2 curves as values of modular functions on the Hilbert moduli space and show how to compute them. We relate them to the usual three Igusa invariants on...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Kristin Lauter
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Bianca Viray
Microsoft Research Video
movies
eye 17
favorite 0
comment 0
3:15 - 3:45 TBAPret-a-Voter: overview and open probelms ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Josh Benaloh
Microsoft Research Video
movies
eye 15
favorite 0
comment 0
After describing some joint work with Menezes in which isogenies are used to show that conventional wisdom about parameter selection might sometimes be wrong, I'll shift gears and make some comments on how easy it is to get things badly wrong in cryptography. I'll illustrate by giving a brief survey of some of the many misjudgments I've made over the years. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, David Harvey
Microsoft Research Video
movies
eye 15
favorite 0
comment 0
The talk is about the derivation of the addition law on an arbitrary elliptic curve and efficiently adding points on this elliptic curve using the derived addition law. The outcomes of this work guarantee practical speedups in higher level operations which depend on point additions. In particular, the contributions immediately find applications in cryptology. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Husevin Hisil
Microsoft Research Video
movies
eye 14
favorite 0
comment 0
Vélu's formulas allow to compute an isogeny between elliptic curves from the coordinates of the points in the kernel. In this talk, I describe an algorithm using theta functions to compute an isogeny from its kernel on any abelian variety. I will give specific timings of a genus 2 implementation, and describe some applications. This is a joint work with Romain Cosset and David Lubicz. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Damien Robert
This talk will report on ongoing work with Barry Mazur that studies 2-Selmer ranks in the family of all quadratic twists of a fixed elliptic curve over a number field. Our goal is to compute the density of twists with a given 2-Selmer rank r, for every r. This has been done by Heath-Brown, Swinnerton-Dyer, and Kane for elliptic curves over Q with all 2-torsion rational. Our methods are different and work best for curves with no rational points of order 2. So far we can prove under certain...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Karl Rubin
Microsoft Research Video
movies
eye 14
favorite 0
comment 0
Despite a decade of research, the problem of securing the global Internet's routing system is far from solved. Indeed, a key hurdle for the transition to secure routing is the fact that the Internet consists of thousands of autonomous systems (e.g. backbone providers like AT&T, content providers like Google, business networks like Bank of America), that will make deployment decisions according to their own local business objectives. Worse yet, the security benefits provided by secure...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Sharon Goldberg
Microsoft Research Video
movies
eye 13
favorite 0
comment 0
An amicable pair for an elliptic curve E/Q is a pair of primes (p,q) of good reduction for E satisfying #E(Fp) = q and #E(Fq) = p. Aliquot cycles are analogously defined longer cycles. Although rare for non-CM curves, amicable pairs are – surprisingly – relatively abundant in the CM case. We present heuristics and conjectures for the frequency of amicable pairs and aliquot cycles, and some results for the CM case (including the especially intricate j=0 case). We present some open problems...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Kate Stange
Microsoft Research Video
movies
eye 12
favorite 0
comment 0
In this talk I will describe how to do Sage development,which will help you be more prepared for the coding sprints. I'llexplain how to make a trac ticket, format your code, save and postcode to trac, etc. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, William Stein
Microsoft Research Video
movies
eye 12
favorite 0
comment 0
1:45 - 2:15 Josh Benaloh, Microsoft ResearchVerified Optical Scan: overview and open probelms ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Josh Benaloh
Microsoft Research Video
movies
eye 11
favorite 0
comment 0
The embedded security community has been looking at the ECC ever since it was introduced. Hardware designers are now challenged by limited area (15k Gates), low power budget (100uw) and sophisticated physical attacks. This talk will report the state-of-the-art ECC implementations for ultra-constrained devices. We take a passive RFID tag as our potential target. We will discuss the known techniques to realize ECC on such kind of devices, and what are the challenges we face now and in the near...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Junfeng Fan
Microsoft Research Video
movies
eye 11
favorite 0
comment 0
2:30 - 3:00 Ben Adida, Harvard Medical SchoolHelios: overview and open problems ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Ben Adida
Microsoft Research Video
movies
eye 10
favorite 0
comment 0
11:30 - 12:30 Ben Adida, Harvard Medical SchoolIntroduction to verifiable election technologies ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, Ben Adida
Segment I 9:00 – 10:50 amWelcome and remarksPoint Obfuscation and FriendsRan Canetti, Tel Aviv UniversityA point program is a program that accepts a single input and rejects all other inputs. A point obfuscator takes a point program (in a certain format) and turns it into a program with the same functionality, but where the program itself does not provide any additional information on the special point that cannot be deduced from simply running the program as a black box.We will review some...
Topics: Microsoft Research, Microsoft Research Video Archive, Kristin Lauter, John Manferdelli, Ran...